package algorithm.dynamicProgramming.p343;

import java.util.Arrays;

/**
 * 343. 整数拆分
 */
class Solution_v1 {
    private int[] memo;
    public int integerBreak(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return breakInteger(n);
    }

    // 将n进行分割（至少分割成两部分），可以获得的最大乘积
    private int breakInteger(int n) {
        if (n == 1) {
            return 1;
        }

        if (memo[n] != -1) {
            return memo[n];
        }

        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            // 将n分割为 i 和 n - i，
            // 比较 res , i * (n - i), i * breakInteger(n - i) 取三者的较大者
            res = Math.max(res, i * (n - i));
            res = Math.max(res, i * breakInteger(n - i));
        }

        memo[n] = res;

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().integerBreak(10));
    }
}